package Sort;

/**
 * @author Liangyaoyun
 */
public class MyMergeSort {
    private void mergeSort(int[] nums){
        int[] numsSorted=new int[nums.length];
        mergeSortInner(nums,numsSorted,0, nums.length-1);
    }

    public void mergeSortInner(int[] nums,int[] numsSorted,int left,int right){
        if (left==right){
            return;
        }
        int mid=(left+right)/2;
        int i=left;
        int j=mid+1;
        int k=left;

        mergeSortInner(nums,numsSorted,left,mid);
        mergeSortInner(nums,numsSorted,mid+1,right);

        while (i<=mid&&j<=right){
            if (nums[i]<=nums[j]){
                numsSorted[k]=nums[i];
                i++;
            }else {
                numsSorted[k]=nums[j];
                j++;
            }
            k++;
        }
        while (i<=mid){
            numsSorted[k]=nums[i];
            i++;
            k++;
        }
        while (j<=right){
            numsSorted[k]=nums[j];
            j++;
            k++;
        }
        for (int l = left; l <=right ; l++) {
            nums[l]=numsSorted[l];
        }
    }

    public static void main(String[] args) {
        MyMergeSort myMergeSort=new MyMergeSort();
        int[] nums=new int[]{1,3,4,5,4,9,5,2,3};
        myMergeSort.mergeSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
